//给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。 
//
// 
//
// 示例： 
//
// 给出如下 3x6 的高度图:
//[
//  [1,4,3,1,3,2],
//  [3,2,1,3,2,4],
//  [2,3,3,2,3,1]
//]
//
//返回 4 。
// 
//
// 
//
// 如上图所示，这是下雨前的高度图[[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] 的状态。 
//
// 
//
// 
//
// 下雨后，雨水将会被存储在这些方块中。总的接雨水量是4。 
//
// 
//
// 提示： 
//
// 
// 1 <= m, n <= 110 
// 0 <= heightMap[i][j] <= 20000 
// 
// Related Topics 堆 广度优先搜索 
// 👍 294 👎 0
#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

class UnionFind {
public:
    vector<int> parent;
    vector<int> size;
    int n;
    int setCount;
public:
    UnionFind(int _n) : n (_n),setCount(_n),parent(_n),size(_n,1){
        //iota(parent.begin(),parent.end(),0);
        for (int i = 0; i < _n; ++i) {
            parent[i] = i;
        }
    }

    int findSet(int x){
        return parent[x] == x ? x : findSet(parent[x]);
    }

    bool uniteSet(int x ,int y){
        int x0 = findSet(x);
        int y0 = findSet(y);
        if (x0 == y0){
            return false;
        }
        if (size[x0] < size[y0]){
            swap(x0,y0);
        }
        parent[y0] = x0;
        size[x0] += size[y0];
        --setCount;
        return true;
    }

    bool connected(int x,int y){
        int x0 = findSet(x);
        int y0 = findSet(y);

        return x0 == y0;
    }

};


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        
    }
};
//leetcode submit region end(Prohibit modification and deletion)
